package linear_list.leetcode.easy;

/**
 * @author Stark
 * @description 相交链表
 * 题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 * @date 2022/4/10 23:09
 **/
public class Num160_GetIntersectionNode {
    int choice = 1;
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(choice == 1) {
            //使用两个指针,cur1从headA出发,cur2从headB出发
            //当走到null时,改变指针的指向,有从另一个头结点开始遍历
            //两个指针是同时往后移动一步
            //相交结点个数为n,没有则为0
            //lA表示从headA开始走到相交结点的路程,如果没有相交链表,则表示以headA为头结点的链表的长度
            //lB同理表示.
            //cur1的路程为lA + n + lB
            //cur1的路程为lB + n + lA
            //可见,两个索引走的路程是一样的,而且都是每次移动一步,所以必然同时走到null(n为0)
            //或者同时走到相交结点处
            //最后直接返回其中一个指向即可
            ListNode cur1 = headA, cur2 = headB;
            while (cur1 != cur2) {
                cur1 = cur1 == null ? headB : cur1.next;
                cur2 = cur2 == null ? headA : cur2.next;
            }
            return cur1;
        }
        else if(choice == 2) {
            ListNode cur1 = headA, cur2 = headB;
            return getIntersectionNodeRecursion(headA,headB,cur1,cur2);
        }
        return null;
    }

    private ListNode getIntersectionNodeRecursion(ListNode headA, ListNode headB, ListNode cur1, ListNode cur2) {
        if(cur1 == cur2)
            return cur1;
        return getIntersectionNodeRecursion(headA,headB,
                cur1 == null ? headB : cur1.next,cur2 == null ? headA : cur2.next);
    }
}
